/*
 * @lc app=leetcode.cn id=993 lang=typescript
 *
 * [993] 二叉树的堂兄弟节点
 */

// @lc code=start

// Definition for a binary tree node.
// class TreeNode {
//   val: number;
//   left: TreeNode | null;
//   right: TreeNode | null;
//   constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
//     this.val = val === undefined ? 0 : val;
//     this.left = left === undefined ? null : left;
//     this.right = right === undefined ? null : right;
//   }
// }

class Data {
  node: TreeNode;
  parent: TreeNode;
  depth: number;
  constructor(node: TreeNode | null = null, parent: TreeNode | null = null, depth: number = 0) {
    this.node = node;
    this.parent = parent;
    this.depth = depth;
  }
}

function isCousins(root: TreeNode | null, x: number, y: number): boolean {
  let xnode: Data = null;
  let ynode: Data = null;
  const queue = [];
  // 初始化
  queue.push(new Data(root, null, 0));
  while (queue.length) {
    const data = queue.shift();
    if (data.node.val === x) xnode = data;
    if (data.node.val === y) ynode = data;
    if (xnode !== null && ynode !== null) break;
    if (data.node.left) queue.push(new Data(data.node.left, data.node, data.depth + 1));
    if (data.node.right) queue.push(new Data(data.node.right, data.node, data.depth + 1));
  }
  // console.log(xnode, ynode);
  return xnode.depth === ynode.depth && xnode.parent !== ynode.parent;
}
// @lc code=end
